package main

import (
	"fmt"
	"sort"
)

/*
300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
*/

/*
动态规划：把从开始到每个位置的最大连续子序列长度都统计出来，没到一个数，用比他小的最大子序列+1
动态规划表达式：

	f(i) 表示从头开始到 i 位置的最长严格递增子序列的长度

动态规划方程：

	f(i) = max{f(0)~f(i-1)}+1
*/
func lengthOfLIS1(nums []int) int {
	f := make([]int, len(nums))
	res := 0
	for i := range nums {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				f[i] = max(f[i], f[j])
			}
		}
		f[i] += 1
		res = max(res, f[i])
	}
	return res
}

/*
无限奇妙的折半查找
用一个数组接受保存最长严格递增子序列的长度：
每个数都拿到数组中查找他应该保存在这个数组中的位置，然后把它保存到对应的位置；
跑完所有数以后，数组的长度就是需要的最长严格递增子序列的长度
*/
func lengthOfLIS2(nums []int) int {
	f := make([]int, 0, len(nums)) // 最长也就所有数都是有序的呗
	var i int
	for _, num := range nums {
		i = sort.SearchInts(f, num)
		if i >= len(f) {
			f = append(f, num)
		} else {
			f[i] = num
		}
		fmt.Println(f)
	}
	return len(f)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {

	nums := []int{10, 9, 2, 5, 3, 18, 101, 18, 20}
	fmt.Println(lengthOfLIS1(nums))
	fmt.Println(lengthOfLIS2(nums))

}
